package com.yang.String_;

public class LeetCode459 {
    public static void main(String[] args) {
        SolutionLeetCode459 solutionLeetCode459 = new SolutionLeetCode459();
        String  s = "abcabcabcabc";
        boolean b = solutionLeetCode459.repeatedSubstringPattern(s);
        System.out.println(b);
    }
}

class SolutionLeetCode459 {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        int[] next = new int[len];
        // 初始化next数组
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            // 一直循环知道j跳到相等的前后缀处 最多跳到0
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
                // 当遇到不相同的就往(最近相同前后缀)回跳一次
                j = next[j];
            }
            // 如果相同就继续往前比较
            if( s.charAt(i) == s.charAt(j+1)) {
                j++;
            }
            // 前缀表记录当前最长相同前后缀长度
            next[i] = j;
        }
        // next[len-1]+1 是此时最长相同前后缀的长度
        if(next[len-1] > -1 && len % (len - (next[len-1]+1))==0 ){
            return true;
        }
        return false;
    }
}
